perm filename REDUCE.XER[CSP,DOC] blob
sn#002724 filedate 1972-10-09 generic text, type T, neo UTF8
STANFORD ARTIFICIAL INTELLIGENCE PROJECT October 1970
MEMO AIM-133
R E D U C E 2
U S E R ' S M A N U A L*
by
Anthony C. Hearn
University of Utah
*This research was sponsored by the Advanced Research Projects Agency
of the Department of Defense under Contract No. F30602-70-C-0300 at
the University of Utah, and under Contract No. SD-183 at Stanford
University.
ABSTRACT
This manual provides the user with a description of the
algebraic programming system REDUCE 2. The capabilities of this
system include:
1) Expansion and ordering of rational functions of polynomials,
2) symbolic differentiation of rational functions of polynomials
and general functions,
3) substitutions and pattern matching in a wide variety of forms,
4) calculation of the greatest common divisor of two polynomials,
5) automatic and user controlled simplification of expressions,
6) calculations with symbolic matrices,
8) a complete language for symbolic calculations, in which the
REDUCE program itself is written,
9) calculations of interest to high energy physicists including
spin 1/2 and spin 1 algebra,
10) tensor operations.
%TOP,,,,i
TABLE OF CONTENTS
1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1
2. STRUCTURE OF PROGRAMS. . . . . . . . . . . . . . . . . . . . . . 2-1
2.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 2-1
2.2 Numbers . . . . . . . . . . . . . . . . . . . . . . . . 2-1
2.3 Identifiers . . . . . . . . . . . . . . . . . . . . . . 2-2
2.4 Variables . . . . . . . . . . . . . . . . . . . . . . . 2-2
2.4.1 Reserved Variables. . . . . . . . . . . . . . . . . . 2-2
2.5 Operators . . . . . . . . . . . . . . . . . . . . . . . 2-3
2.5.1 DF. . . . . . . . . . . . . . . . . . . . . . . . . . 2-6
2.5.2 COS. LOG. SIN . . . . . . . . . . . . . . . . . . . . 2-7
2.5.3 SUB . . . . . . . . . . . . . . . . . . . . . . . . . 2-7
2.6 Strings . . . . . . . . . . . . . . . . . . . . . . . . 2-8
2.7 Comments . . . . . . . . . . . . . . . . . . . . . . . 2-8
2.8 Expressions . . . . . . . . . . . . . . . . . . . . . . 2-8
2.8.1 Numerical Expressions . . . . . . . . . . . . . . . . 2-9
2.8.2 Scalar Expressions . . . . . . . . . . . . . . . . . . 2-9
2.8.3 Boolean Expressions . . . . . . . . . . . . . . . . . 2-9
2.8.4 Equations . . . . . . . . . . . . . . . . . . . . . .2-10
2.9 Reserved Words . . . . . . . . . . . . . . . . . . . .2-10
2.10 Statements . . . . . . . . . . . . . . . . . . . . . .2-10
2.10.1 Assignment Statements. . . . . . . . . . . . . . . .2-11
2.10.2 Conditional Statements . . . . . . . . . . . . . . .2-12
2.10.3 FOR Statements . . . . . . . . . . . . . . . . . . .2-12
2.10.4 GO TO Statements . . . . . . . . . . . . . . . . . .2-14
2.10.5 Compound Statements. . . . . . . . . . . . . . . . .2-15
2.10.6 RETURN Statements. . . . . . . . . . . . . . . . . .2-15
2.11 Declarations . . . . . . . . . . . . . . . . . . . . .2-16
2.11.1 Variable Type Declarations . . . . . . . . . . . . .2-16
2.11.2 Array Declarations . . . . . . . . . . . . . . . . .2-17
2.11.3 Mode Handling Declarations . . . . . . . . . . . . .2-17
2.12 Commands . . . . . . . . . . . . . . . . . . . . . . .2-17
2.13 File Handling Commands . . . . . . . . . . . . . . . .2-18
2.13.1 IN . . . . . . . . . . . . . . . . . . . . . . . . .2-18
2.13.2 OUT. . . . . . . . . . . . . . . . . . . . . . . . .2-18
2.13.3 SHUT . . . . . . . . . . . . . . . . . . . . . . . .2-19
2.14 Substitution Commands. . . . . . . . . . . . . . . . .2-19
2.15 Removing Assignments and Substitution Rules from
Expressions. . . . . . . . . . . . . . . . . . . . .2-22
2.16 Adding Rules for Differentiation of User-defined
Operators. . . . . . . . . . . . . . . . . . . . . .2-22
2.17 Procedures . . . . . . . . . . . . . . . . . . . . . .2-23
2.18 Commands Used in Interactive Systems . . . . . . . . 2-25
2.19 END. . . . . . . . . . . . . . . . . . . . . . . . . 2-26
3. MANIPULATION OF ALGEBRAIC EXPRESSIONS. . . . . . . . . . . . . . 3-1
3.1 The Expression Workspace . . . . . . . . . . . . . . . 3-1
3.2 Output of Expressions . . . . . . . . . . . . . . . . . 3-2
3.2.1 ORDER . . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.2.2 FACTOR . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.2.3 Output Control Flags . . . . . . . . . . . . . . . . 3-4
3.2.4 Output of Strings . . . . . . . . . . . . . . . . . . 3-7
3.2.5 Suppression of Zeros . . . . . . . . . . . . . . . . 3-8
3.3 User Control of the Evaluation Process. . . . . . . . . 3-8
3.4 Cancellation of Common Factors. . . . . . . . . . . . . 3-9
3.5 Numerical Evaluation of Expressions . . . . . . . . . . 3-9
3.6 Saving Expressions for Later Use as Input . . . . . . .3-12
3.7 Partitioning Expressions . . . . . . . . . . . . . . .3-12
4. MATRIX CALCULATIONS. . . . . . . . . . . . . . . . . . . . . . . 4-1
4.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 4-1
4.2 MAT . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1
4.3 Matrix Variables. . . . . . . . . . . . . . . . . . . . 4-1
4.4 Matrix Expressions. . . . . . . . . . . . . . . . . . . 4-2
4.5 Operators with Matrix Arguments . . . . . . . . . . . . 4-3
4.5.1 DET . . . . . . . . . . . . . . . . . . . . . . . . . 4-3
4.5.2 TRACE . . . . . . . . . . . . . . . . . . . . . . . . 4-3
4.6 Matrix Assignments. . . . . . . . . . . . . . . . . . . 4-4
4.7 Evaluating Matrix Elements. . . . . . . . . . . . . . . 4-4
5. ADVANCED COMMANDS. . . . . . . . . . . . . . . . . . . . . . . . 5-1
5.1 Kernels . . . . . . . . . . . . . . . . . . . . . . . . 5-1
5.2 Substitutions for General Expressions . . . . . . . . . 5-2
5.3 Asymptotic Commands . . . . . . . . . . . . . . . . . . 5-5
6. SYMBOLIC MODE . . . . . . . . . . . . . . . . . . . . . . . . . 6-1
6.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 6-1
6.2 General Identifiers . . . . . . . . . . . . . . . . . . 6-2
6.3 Symbolic Infix Operators. . . . . . . . . . . . . . . . 6-2
6.4 Symbolic Expressions. . . . . . . . . . . . . . . . . . 6-3
6.5 Quoted Expressions. . . . . . . . . . . . . . . . . . . 6-3
6.6 LAMBDA Expressions. . . . . . . . . . . . . . . . . . . 6-4
6.7 Symbolic Assignment Statements. . . . . . . . . . . . . 6-4
6.8 Communication with Algebraic Mode. . . . . . . . . . . . 6-6
APPENDIX A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1
A.1 Reserved Identifiers. . . . . . . . . . . . . . . . . . A-1
A.2 Commands Normally Available in REDUCE . . . . . . . . . A-2
A.3 Mode Flags in REDUCE. . . . . . . . . . . . . . . . . . A-5
A.4 Diagnostic and Error Messages in REDUCE . . . . . . . . A-6
A.4.1 Error Messages. . . . . . . . . . . . . . . . . . . . A-6
A.4.2 Diagnostic Messages . . . . . . . . . . . . . . . . . A-8
APPENDIX B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B-1
B.1 Running REDUCE on the Stanford PDP-10 . . . . . . . . . B-1
B.2 Running REDUCE on the Stanford IBM 360/67 . . . . . . . B-5
APPENDIX C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-1
Calculations in High Energy Physics . . . . . . . . . . . . . . C-1
C.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . C-1
C.2 Operators Used in High Energy Physics Calculations. . . C-1
C.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . C-1
C.2.2 G . . . . . . . . . . . . . . . . . . . . . . . . . . C-2
C.2.3 EPS . . . . . . . . . . . . . . . . . . . . . . . . . C-3
C.3 Vector Variables. . . . . . . . . . . . . . . . . . . . C-4
C.4 Additional Expression Types . . . . . . . . . . . . . . C-4
C.4.1 Vector Expressions. . . . . . . . . . . . . . . . . . C-4
C.4.2 Dirac Expressions . . . . . . . . . . . . . . . . . . C-5
C.5 Trace Calculations . . . . . . . . . . . . . . . . . . C-5
C.6 Mass Declarations . . . . . . . . . . . . . . . . . . . C-7
C.7 Example . . . . . . . . . . . . . . . . . . . . . . . . C-7
REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R-1
%TOP,,,,1-1
1. INTRODUCTION
REDUCE is a program designed for general algebraic
computations of interest to mathematicians, physicists and engineers.
Its capabilities include:
1) Expansion and ordering of rational functions of polynomials,
2) symbolic differentiation of rational functions of polynomials
and general functions,
3) substitutions and pattern matching in a wide variety of forms,
4) calculation of the greatest common divisor of two polynomials,
5) automatic and user controlled simplification of expressions,
6) calculations with symbolic matrices,
8) a complete language for symbolic calculations, in which the
REDUCE program itself is written,
9) calculations of interest to high energy physicists including
spin 1/2 and spin 1 algebra,
10) tensor operations.
There are several levels at which REDUCE may be used and
understood. The beginning user can acquire an operating knowledge of
the system by studying Section 2 of this manual, which contains
details of the basic structure of programs. Having mastered this, he
should then study Section 3, which describes the facilities available
for manipulating algebraic expressions. A more advanced user must
understand Sections 4 and 5, which describe the matrix handling
routines and some advanced commands. Finally, to become a complete
expert, the user will have to learn LISP 1.5 and study the material
on the symbolic mode of operation in Section 6.
Additional material of interest may be found in the
Appendices. Appendix A gives the user a useful summary of the system
commands and other properties of the system. Appendix B gives
instructions for using REDUCE at various computer installations. This
information may of course need modification for your computer.
Finally, Appendix C contains details of the high energy physics
commands for those interested.
The author would appreciate hearing from any users who
experience trouble with the system (please include copies of relevant
input and output). Acknowledgment of the use of REDUCE in any
published calculations would also be appreciated. The author would
also be grateful for a copy of any such publication.
%TOP,,,,2-1
2. STRUCTURE OF PROGRAMS
2.1 Preliminary
A REDUCE program consists of a set of functional commands
which are evaluated sequentially by the computer. These commands are
composed from declarations, statements and expressions, which in turn
are sequences of numbers, variables, operators, strings, reserved
words and delimiters (such as commas and parentheses).
2.2 Numbers
Numbers in REDUCE may be of two types; integer and real.
Integers consist of a signed or unsigned sequence of decimal digits
written without a decimal point.
e. g. -2, 5396, +32
There is no practical limit on the number of digits permitted as
arbitrary precision arithmetic is used.
Real numbers may be written in two ways;
i) as a signed or unsigned sequence of 1-9 decimal digits with
an embedded decimal point.
ii) as in 1) followed by a decimal exponent which is written as
the letter E followed by a signed or unsigned integer.
e. g. 32. +32.0 0.32E2 and 320.E-1 are all representations of 32.
Restriction:
The unsigned part of any number may NOT begin with a decimal point.
i. e. NOT ALLOWED .5 -.23 +.12
2.3 Identifiers
Identifiers in REDUCE consist of one to twenty-four
alphanumeric characters (i.e. upper case alphabetic letters or
decimal digits) the first of which must be alphabetic.
e. g. A AZ P1 Q23P AVERYLONGVARIABLE
Identifiers are used as variables, labels and to name arrays,
operators and procedures.
Restrictions:
Reserved words in REDUCE (see Section 2.9) may not be used as
identifiers. No spaces may appear within an identifier, and an
identifier may not extend over a line of text.
2.4 Variables
Variables are a particular type of identifier, and are
specified by name and type. Their names must be allowed
identifiers. There are several variable types allowed, and these
are discussed later, beginning in Section 2.11.1.
2.4.1 Reserved Variables
Several variables in REDUCE have a particular value which
cannot easily be changed by the user. These variables are as
follows:
I square root of -1. All powers of I are
automatically replaced by the appropriate
combination of -1 and I.
E base of natural logarithms
2.5 Operators
Operators in REDUCE are also specified by name and type.
There are two types, infix and prefix.
Infix operators occur between their arguments.
e. g. A + B - C
B↑2/3-U
The following infix operators are built into the system.
<infix operator> ::= ←|∧|∨|¬|=|≠|>=|>|<=|<|+|-|*|/|↑
For compatibility with the intermediate language used by
REDUCE, each infix operator has an alphanumeric identifier associated
with it. These identifiers may be used interchangably with the
corresponding infix character(s) on input. This correspondence is as
follows:
← SETQ
∧ AND
∨ OR
¬ NOT
= EQUAL
≠ UNEQ
>= GREATEQ
> GREATERP
<= LESSEQ
< LESSP
+ PLUS
- MINUS
* TIMES
/ QUOTIENT
↑ EXPT
In systems which do not have all these characters, the
alphanumeric name may be used instead. In addition, the following
alternative forms are allowed
operator alternative
↑ **
← :=
These operators may be further divided into the following sub
classes
<logical operator> ::= ∧|∨|¬
<relational operator> ::= =|≠|>=|>|<=|<
<arithmetic operator> ::= +|-|*|/|↑
The above operators may take any number of arguments, except
- which is unary, and ↑ and / which are binary. The expression A-B
is interpreted as A+-B on input. Furthermore, A↑B↑C↑D is interpreted
as A↑(B↑(C↑D)) and similarly with /.
Parentheses may be used to specify the order of combination. If
parentheses are omitted then this order is by the precedence ordering
given by the above list (from outermost to innermost operations).
The user may add new single character infix operators to the system
by the declaration INFIX.
e. g. INFIX ∀,∃; adds infix operators ∀ and ∃ to the system.
These new operators will be given a precedence lower than any
existing infix operator except ← (which always has the lowest
precedence) and will be ordered among themselves by their order at
definition. Thus ∀ has a higher precedence than ∃.
Restriction:
The infix characters λ, !, ε, ≡ and . have reserved uses in
REDUCE and cannot be declared as infix operators by the user.
The precedence of any infix operator except ← may be changed
by the declaration PRECEDENCE.
e. g. PRECEDENCE ∀,=;
gives ∀ a new precedence immediately higher than the current
precedence of =.
Prefix operators occur at the head of their arguments, which
are written as a list enclosed in parentheses and separated by
commas, as with normal mathematical functions.
e. g. COS(U)
DF(X↑2,X)
Parentheses may be omitted if the operator is unary.
e. g. COS Y and COS (Y) are equivalent.
Such unary operators have a precedence higher than any infix operator.
Infix operators may also be used in a prefix format on input.
On output, however, they will always be printed in an infix form.
Some prefix operators are also built into the system. These
are as follows:
2.5.1 DF
The operator DF is used to represent partial differentiation
with respect to one or more variables. The first argument is the
scalar expression to be differentiated. The remaining arguments
specify the differentiation variables and the number of times they
are applied by the following syntax:
DF(<expression>,<variable>,<number>,...,<variable>,<number>)
The <number> may be omitted if it is 1.
e. g. DF(Y,X) ≡ ∂Y/∂X
2 2
DF(Y,X,2) ≡ ∂ Y/∂X
5 2 2
DF(Y,X1,2,X2,X3,2) ≡ ∂ Y/∂X1 ∂X2∂X3
2.5.2 COS, LOG, SIN
These elementary functions are included in the system with
the following properties:
COS (-X) = COS (X)
SIN (-X) = - SIN (X)
COS (O) = 1
SIN (O) = 0
LOG (E) = 1
LOG (1) = 0
The user can add further rules for the reduction of
expressions involving these operators by the methods described in
Sections 2.14 and 5.2.
2.5.3 SUB
This operator is described in Section 2.14.
The user may add new prefix operators to the system by the
declaration OPERATOR.
e. g. OPERATOR H, G1, ARCTAN;
adds the prefix operators H, G1 and ARCTAN to the system.
2.6 Strings
Strings are used only in output statements. A string consists
of any number of characters enclosed in double quotes.
e. g. "A STRING".
2.7 Comments
Comments are useful for including explanatory material at
various points in a program. They may be used in the following form:
COMMENT <any sequence of characters not including a terminator>
<terminator>
where
<terminator> ::= ;|$
e. g. COMMENT THIS IS A COMMENT;
In addition, the sequence of symbols
END <any sequence of symbols not including a terminator or the
reserved words END, ELSE or UNTIL>
is equivalent to the reserved word END.
2.8 Expressions
REDUCE expressions may be of several types and consist of
syntactically allowed sequences of numbers, variables, operators,
left and right parentheses and commas. The most common types are as
follows:
2.8.1 Numerical Expressions
These consist of syntactically allowed combinations of
integer or real variables, arithmetic operators and parentheses. They
evaluate to numbers.
Examples:
2
I + J - 2 * I↑2
are numerical expressions if I and J are integers.
2.8.2 Scalar Expressions
These consist of scalar variables and arithmetic operators
and follow the normal rules of scalar algebra.
Examples:
X
X↑3 - 2*Y/(2*Z↑2 - DF(X,Z))
(P↑2 + M↑2)↑(1/2)*LOG (Y/M)
2.8.3 Boolean Expressions
These are expressions which return a truth value. In REDUCE,
the reserved word NIL represent the truth value `false'. Any other
expression represents `true'. So in a sense, any expression is a
boolean expression, because all expressions return a value.
However, a proper boolean expression has the syntactical form:
<expression> <relational operator> <expression>
or
<boolean expression> <logical operator> <boolean expression>
They are used mainly in the IF and FOR statements described in
Sections 2.10.2 and 2.10.3.
Examples:
J<1
X > 0 ∨ X = -2
2.8.4 Equations
In the remainder of this manual, we shall refer to the
expression
<scalar expression> = <scalar expression>
as an equation.
2.9 Reserved Words
Certain words are reserved in REDUCE. They may only be used
in the manner described in this manual. These words are as follows:
<reserved word> ::= BEGIN|DO|ELSE|END|FOR|FUNCTION|IF|LAMBDA|NIL|
PRODUCT|RETURN|STEP|SUM|UNTIL|WHILE
2.10 Statements
A statement is any allowed combination of reserved words and
expressions, and has the syntax
<statement> ::= <expression>|<proper statement>
The following sub-sections describe some proper statements in
REDUCE.
2.10.1 Assignment Statements
These statements have the following syntax
<assignment statement> ::= <expression> ← <statement>
e. g. A1←B+C
H(X,Y)←X-2*Y
By analogy with numerical assignments in ALGOL, an assignment
statement sets the left hand side of the statement to the algebraic
value of the right hand side. Unfortunately, the algebraic
evaluation of an expression is not as unambiguous as the
corresponding numerical evaluation. This algebraic evaluation process
is generally referred to as 'simplification' in the sense that the
evaluation usually but not always produces a simplified form for the
expression. In REDUCE, the default evaluation of an expression
involves expansion of the expression and collection of like terms,
ordering of the terms, evaluation of derivatives and other functions
and substitution for any expressions which have values assigned or
declared (Sections 2.14 and 5.2). In many cases, this is all that the
user needs.
needs.
However, the user can exercise some control over the way in
which the evaluation is performed by various declarations available
to him. These declarations are explained in Section 3.3.
If a real (floating point) number is encountered during
evaluation, the system will normally convert it into a ratio of two
integers, and print a message informing the user of the conversion.
If the user wants to use real arithmetic, he can inhibit this
conversion by the command ON FLOAT;. This use of the ON declaration
is explained in Section 2.11.3.
The results of the evaluation of an expression are printed if
a semicolon is used as a delimiter. Because it is not usually
possible to know in advance how large an expression will be, no
explicit format statements are offered to the user. However, a
variety of output declarations are available so that the output can
be produced in a variety of forms. These output declarations are
explained in Section 3.4.
It is also possible to write an assignment in the form
<expression> ← <expression> ← ... ← <expression> ← <statement>
In this form, each <expression> is set to the value of the <statement>.
2.10.2 Conditional Statements
The conditional statement has the following syntax:
<conditional statement> ::= IF <boolean expression> THEN <statement>
ELSE <statement>
Its use is obvious. The ELSE clause is optional.
2.10.3 FOR Statements
The FOR statement is used to define a variety of program
loops. Its general syntax is as follows:
FOR <variable>←<arithmetic expression> STEP <arithmetic expression>
{DO <statement>
{UNTIL <arithmetic expression>} {
{ } {SUM <algebraic expression>
{WHILE <boolean expression> } {
{PRODUCT <algebraic expression>
The DO version of the FOR statement is the normal ALGOL
useage, and is similar to the FORTRAN DO statement. It does not
return an algebraic value. The SUM and PRODUCT versions
respectively form the sum and product of the relevant algebraic
expression over the defined range. They return the value of the
computed sum or product. Note, however, that this value is NOT
printed. It will be printed, however, if the statement is assigned as
the value of an expression and a semicolon used as a terminator.
The <variable> within the FOR statement is declared INTEGER
if it is not already. Its value during the calculation of the
statement is independent of its value outside, so that I can be used
in this context, even though I normally stands for the square root of
-1.
Examples:
We assume that the declaration ARRAY A(10); has been made in the
following examples. This declaration is explained in Section 2.11.2.
(i) To set each element A(I) of the array to X↑I we could write
FOR I←0 STEP 1 UNTIL 10 DO A(I)←X↑I$
As a further convenience, the common construction
STEP 1 UNTIL
may be abbreviated by a colon. Thus we could write instead of the
above
FOR I←0:10 DO A(I)←X↑I$
(ii) To sum the squares of the even positive integers through 50, we
could write
FOR I←2 STEP 2 UNTIL 50 SUM I↑2;
As explained above, the result is not printed in this case. However,
it is held in the expression workspace (see Section 3.1) and can be
retrieved from there if required.
(iii) To set X to the factorial of 10 we could write
X ← FOR I←1:10 PRODUCT I;
Alternatively, we could set the element A(I) to I! by the
statements
A(0)← 1$ FOR I←1:10 DO A(I)←I*A(I-1)$
2.10.4 GO TO Statements
GO TO (or GOTO) statements are used to perform an
unconditional transfer to a label in a compound statement (Section
2.10.5). They have the syntax:
<go to statement> ::= GO TO <label>
<label> ::= <variable>
Restriction:
GO TO statements may only occur within a compound statement. They may
NOT occur at the top level of your program.
2.10.5 Compound Statements
A compound statement is defined by the following syntax
<compound statement> ::= BEGIN <compound tail>
<compound tail> ::= <unlabeled compound tail>
|<label>:<compound tail>
<unlabeled compound tail> ::= <statement> END
| <statement> <terminator> <compound tail>
<label> ::= <identifier>
<terminator> ::= ;|$
e. g. X ← BEGIN INTEGER M;
M←1$
L1: IF N=0 THEN RETURN M;
M←M*N$
N←N-1$
GO TO L1
END OF BLOCK;
will assign the factorial of a preassigned INTEGER N to X.
2.10.6 RETURN Statements
The RETURN statement allows for a transfer out of a compound
statement to the next highest program level. It may be used alone,
in which case the statement returns NIL.
e. g., RETURN (X+Y);
RETURN M;
RETURN;
Restriction:
RETURN statements may only occur within a compound statement.They may
NOT occur at the top level of your program.
2.11 Declarations
Declarations are a particular type of statement used to set
flags, make type declarations and define procedures. PROCEDURE
declarations are discussed in Section 2.17. Some other REDUCE
declarations are described in the following sub-sections.
2.11.1 Variable Type Declarations
These declarations tell the system how various identifiers
are to be processed. Types allowed include INTEGER, REAL and SCALAR.
e. g. INTEGER M,N;
REAL M1;
SCALAR X,Y;
Type declarations may be made at any level in a program, and apply
only to the particular program block in which they occur. Variables
not declared are assumed SCALAR. This is the basic symbolic variable
type.
2.11.2 Array declarations
Arrays in REDUCE are defined similar to FORTRAN dimension
statements.
e. g. ARRAY A(10),B(2,3,4);
Their indices each range from 0 to the value declared. An element of
an array is referred to in standard FORTRAN notation,
e. g. A(2)
Array elements may appear in the left side of assignment statements
as in the examples in Section 2.10.3.
2.11.3 Mode Handling Declarations
Two declarations are offered to the user for turning on or
off a variety of flags in the system. The declarations ON and OFF
take a list of flag names as argument and turn them on and off
respectively.
e. g. ON FLOAT,GCD;
OFF LIST;
The use of these flags and others available to the user is
explained later in this manual.
2.12 Commands
A command is an order to the system to do something. It has
the syntax
<command> ::= <statement><terminator>|<proper command>
<proper command> ::= <command name><space>
<statement>,...,<statement><terminator>
A variety of commands are discussed in the sections which follow.
2.13 File Handling Commands
In many applications, it is desirable to load previously
prepared REDUCE files into the system, or to write output on varying
devices. REDUCE offers three commands for this purpose, namely, IN,
OUT, and SHUT.
2.13.1 IN
This command takes a list of file names as argument and
directs the system to input each file (which should contain REDUCE
commands) into the system. A file name will have a varying syntax
from implementation to implementation, but in many cases will be an
identifier.
e. g. IN F1,GGG; will load the files F1 and GGG.
When input comes from an external file, statements are echoed
on the output device as they are read. If this facility is not
required, the echoing can be prevented by turning off the flag ECHO
in the relevant file.
2.13.2 OUT
This command takes a single file name as argument, and
directs output to that file from then on. If the file has previously
been used for output during the current job, the output is appended
to the end of the file. An existing file is erased before its first
use for output in a job.
To output on the terminal without closing the output file,
the reserved file name T (for terminal) may be used.
e. g. OUT OFILE; will direct output to the file OFILE and
OUT T; will direct output the user's terminal.
2.13.3 SHUT
This command is used to close an output file at completion.
Most systems require this action by the user, otherwise output may be
lost. If a file is shut and a further OUT command issued for the
same file, the file is erased before the new output is written.
2.14 Substitution Commands
An important class of commands in REDUCE is that class which
defines substitutions for variables and expressions to be made during
the evaluation of expressions. Such substitutions may be declared
globally by the command LET and locally by use of the operator SUB.
LET is used in the form
LET <substitution list>;
where <substitution list> is a list of equations of the form:
<variable> = <expression>
or <prefix operator> (<argument>,...,<argument>) = <expression>
or <argument> <infix operator>,..., <argument> = <expression>
e. g. LET X = Y↑2 + 2,
H(X,Y) = X - Y,
COS(60) = 1/2,
Y↑3 = 2*Z - 3;
These substitutions will now be made for all such variables and
expressions appearing in evaluations. Any operators occuring in such
equations will be automatically declared OPERATOR by the system.
In each of these examples, substitutions are only made for
the explicit expressions given; i.e., none of the variables may be
considered arbitrary in any sense.
For example, the command
LET H(X,Y) = X - Y;
will replace H(X,Y) by X - Y, but not H(X,Z) or any other function of
H. If a substitution for all possible values of a given argument of
an operator is required, the declaration FOR ALL (or FORALL) may be
used. The syntax of such a command is
FOR ALL <variable>,...,<variable> <LET command><terminator>
e. g. FOR ALL X,Y LET H(X,Y) = X-Y;
FOR ALL X LET K(X,Y) = X↑Y;
If the left hand side of an equation is redefined by a later
call of LET, the previous expression is replaced by the new one, and
a diagnostic message printed to inform the user. Such messages may
be inhibited by turning off the flag MSG.
In applying any substitutions set up by LET, the system
searches the substitution expression itself for any expressions which
may themselves have substitutions declared for them. Thus LET sets
up an equivalence between the left hand side of the substitution and
the right hand side rather than an assignment as made by an
assignment statement. In other words, a substitution such as
LET X = X + 1;
is not allowed, since in substituting for X, the system will find
that the variable X in the substitution expression itself has a
substitution and a push-down-list overflow error will ultimately
result. Similarly, a pair of substitutions
LET L = M + N, N = L + R;
are not allowed.
On the other hand, if the user wishes simply to replace every
occurrence of a variable by any expression without checking that
expression again for further substitutions, the operator SUB may be
used. Its general form is
SUB (<substitution list>,<expression>)
as in
SUB(X=X+1, Y=1, X**2+Y**2)
This substitution is made by first simplifying the <expression>, then
replacing any variables occurring on the substitution list, and
finally resimplifying the result. Thus, in the above example, the
result would be
X**2+2*X+2
2.15 Removing Assignments and Substitution Rules from Expressions
The user may remove all assignments and substitution rules
from any expression by the command CLEAR, in the form
CLEAR <expression>,...,<expression><terminator>
e. g. CLEAR X, H(X,Y);
A whole array, such as A in Section 2.11.2, can be cleared by
the command CLEAR A; An individual element of A can also be cleared
by a command such as CLEAR A(3);
2.16 Adding Rules for Differentiation of User-defined Operators
An extension of the syntax of LET arguments allows for the
introduction of rules for differentiation of user-defined operators.
Its general form is
FOR ALL <var1>,...,<varn>
LET DF(<operator><varlist>,<vari>)=<expression>
where <varlist> ::= (<var1>,...,<varn>)
and <var1>,...,<vari>,...,<varn> are the dummy variable arguments of
<operator>.
An analogous form is allowed for infix operators.
We illustrate this with some examples:
FOR ALL X LET DF(TAN X,X)= SEC(X)↑2;
FOR ALL X,Y LET DF(F(X,Y),X)=2*F(X,Y),
DF(F(X,Y),Y)=X*F(X,Y);
We notice that all dummy arguments of the relevant operator
must be declared arbitrary by the FOR ALL command, and that rules may
be supplied for operators with any number of arguments. If no
differentiation rule appears for any argument in an operator, the
differentiation routines will return an expression in terms of DF as
the result. For example, if the rule for the differentiation of the
second argument of F is not supplied, the evaluation of DF(F(X,Z),Z)
would leave this expression unchanged.
2.17 Procedures
It is often useful to name a statement for repeated use in
calculations with varying parameters, or to define a complete
evaluation procedure for an operator. REDUCE offers a procedural
declaration for this purpose. Its general syntax is:
<procedural type> PROCEDURE <name><varlist>;<statement>;
and
<varlist> ::= (<variable>,...,<variable>)
The types permitted in REDUCE are REAL, INTEGER and ALGEBRAIC. The
default type is ALGEBRAIC. All these procedures are automatically
declared to be operators on definition.
In the present system, no distinction is made in the handling
of these three types, although this may not be true in later versions.
Examples:
(1) The example in Section 2.10.5 could be made into an integer
procedure FAC by the declaration:
INTEGER PROCEDURE FAC (N);
BEGIN INTEGER M;
M←1$
L1: IF N=0 THEN RETURN M;
M←M*N$
N←N-1$
GO TO L1
END;
If we now evaluate FAC (3) we get the result 6.
(2) As an example of an algebraic procedure, we define an operator
LEG of two arguments which evaluates to the Legendre polynomial. We
define this operator as a procedure from the generating function
formula
n |
1 ∂ 1 |
p (x) = --- --- ------------- |
n n! n 2 |
∂y y -2*x*y+1 | y=0
A REDUCE version of this is
ALGEBRAIC PROCEDURE P(N,X);
SUB(Y=0,DF((Y↑2-2*X*Y+1)↑(-1/2),Y,N))/(FOR I←1:N PRODUCT I)$
With this definition, the evaluation of
2*P(2,W)
would result in the output
2
3*W - 1
We can of course omit the word ALGEBRAIC in this procedure
definition as this is the default type.
In order to allow users relatively easy access to the whole
REDUCE source program, system procedures are not protected against
user redefinition. If a procedure is redefined, a message
*** <procedure name> REDEFINED
is printed. If this occurs, and the user is not redefining his own
procedure, he is well advised to rename it!
2.18 Commands Used in Interactive Systems
REDUCE is designed primarily for interactive use with a time-
shared computer, but naturally it can also operate in a batch
processing environment. There is a basic difference, however,
between interactive and batch use of the system. In the former case,
whenever the system discovers an ambiguity at some point in a
calculation, such as a forgotten type assignment for instance, it
asks the user for the correct interpretation. In batch operation, it
is not practical to terminate the calculation at such points and
require resubmission of the job, so the system makes the most obvious
guess of the user's intentions and continues the calculation.
If input is coming from an external file, the system treats
it as a batch processed calculation. If the user desires interactive
response in this case, he can turn on the flag INT in the file.
Likewise, he can turn off INT in the main program if he does not
desire continual questioning from the system.
Two commands are available in REDUCE for use in interactive
computing. The command PAUSE; may be inserted at any point in an
input file. When this command is encountered on input, the system
prints the message CONT? on the user's terminal and halts. If the
user responds Y (for yes), the calculation continues from that point
in the file. On the other hand, if the user responds N (for no),
control is returned to the terminal, and the user can input further
commands. However, later on he can use the command CONT; and control
is then transferred back to the point in the file after the last
pause was encountered.
2.19 END
The command END; is used to end external files which are used
as input to REDUCE. One of its purposes is to turn off the command
echo, which is annoying to a user typing at a terminal. However, it
also does some file control book-keeping, and should therefore not be
omitted.
If an END command is used in the main program, control is
then transferred to LISP.
%TOP,,,,3-1
3. MANIPULATION OF ALGEBRAIC EXPRESSIONS
In this Section, we consider some further system facilities
for the processing of algebraic expressions.
3.1 The Expression Workspace
When an assignment of an algebraic expression is made, or an
expression is evaluated at the top level, the results of the
evaluation are automatically saved in an environment which we shall
refer to as the workspace. In actual fact, the expression is
assigned to a variable *ANS which is available for further
manipulation. In order to input the asterisk as part of the variable
name, however, it must be prefixed by an exclamation mark.
Example:
If we evaluate the expression (X+Y)↑2 and next wish to
differentiate it with respect to Y, we can simply say
DF(!*ANS,Y);
to get the desired answer.
If the user gets tired of typing !*ANS, or wishes to rename
ANY identifier in the system EXCEPT reserved words, he can simply
say:
LET <new name> = <old name>;
e. g. LET WS=!*ANS;
From now on, WS is recognized as !*ANS in all input.
If the user wishes to assign the workspace to a variable or
expression for later use, the command SAVEAS can be used. It has the
syntax
SAVEAS <expression><terminator>
e. g. after the differentiation in the last example, the
workspace holds the expression 2*X+2*Y. If we wish to assign this to
the variable Z we can now say
SAVEAS Z;
If the user wishes to save the expression in a form that
allows him to use some of its variables as arbitrary parameters, the
FOR ALL command can be used.
e. g. FOR ALL X SAVEAS H(X);
with the above expression would mean that H(Z) evaluates to 2*Y+2*Z.
3.2 Output of Expressions
A considerable degree of flexibility is available in REDUCE
in the printing of expressions generated during calculations. As we
mentioned earlier, no explicit format statements are supplied, as
these prove to be of little use in algebraic calculations, where the
size of output or its composition is not generally known in advance.
Instead, REDUCE provides a series of mode options to the user which
should enable him to produce his output in a comprehensible and
possibly pleasing form.
As we mentioned earlier, an algebraic expression is normally
printed in an expanded form, filling the whole output line with
terms. Certain output declarations, however, can be used to affect
this format. These are as follows:
3.2.1 ORDER
The declaration ORDER may be used to order variables on
output. Thus
ORDER X,Y,Z;
orders X ahead of Y, Y ahead of Z and X,Y and Z ahead of other
variables in expressions which follow, and all ahead of variables
appearing in further ORDER assignments, or those not given an order.
The order of variables may be changed by a further call of ORDER, but
then the reordered variables would have an order lower than those in
earlier ORDER calls.
Thus, ORDER X,Y,Z;
ORDER Y,X;
would order Z ahead of Y and X.
3.2.2 FACTOR
This declaration takes a list of identifiers or functional
expressions as argument. FACTOR is not really a factoring command,
but rather a separation command. All terms involving fixed powers of
the declared expressions are printed as a product of the fixed powers
and a sum of the rest of the terms.
All expressions involving a given prefix operator may also be
factored by putting the operator name in the list of factored
identifiers.
e. g. FACTOR X,COS,SIN(X);
causes all powers of X and SIN(X) and all functions of COS to be
factored.
The declaration REMFAC V1,...,VN; removes the factoring flag from the
expressions V1 through VN.
3.2.3 Output Control Flags
In addition to these declarations, the form of the output can
be modified by switching various output control flags using the
declarations ON and OFF. We shall illustrate the use of these flags
by an example, namely the printing of the expression
X↑2*(Y↑2+2*Y)+X*(Y↑2+Z)/(2*A).
The relevant flags are as follows:
(1) ALLFAC. This flag will cause the system to search the
whole expression, or any sub-expression enclosed in
parentheses, for simple multiplicative factors and print
them outside the parentheses. Thus our expression with
ALLFAC off will print as
2 2 2 2
(2*X *Y *A + 4*X *Y*A + X*Y + X*Z)/(2*A)
and with ALLFAC on as
2 2
X*(2*X*Y *A + 4*X*Y*A + Y + Z)/(2*A)
ALLFAC is normally on, and is on in the following examples,
except where otherwise stated.
(2) DIV. This flag makes the system search the denominator of
an expression for simple factors which it divides into the
numerator, so that rational fractions and negative powers
appear in the output. With DIV on, our expression would
print as
2 2 (-1) (-1)
X*(X*Y + 2*X*Y + 1/2*Y *A + 1/2*A *Z)
DIV is normally off.
(3) LIST. This flag causes the system to print each term in
any sum on a separate line. With LIST on, our expression
prints as
2
X*(2*X*Y *A
+ 4*X*Y*A
2
+ Y
+ Z)
/(2*A)
LIST is normally off.
(4) RAT. This flag is only useful with expressions in which
variables are factored with FACTOR. With this mode, the
overall denominator of the expression is printed with each
factored sub-expression. We assume a prior declaration
FACTOR X; in the following output . We first print the
expression with RAT off:
2 2
(2*X *Y*A*(Y + 2) + X*(Y + Z))/(2*A)
With RAT on the output becomes:
2 2
X *Y*(Y + 2) + X*(Y + Z)/(2*A)
RAT is normally off.
Next, if we leave X factored, and turn on both DIV and
RAT, the result becomes
2 (-1) 2
X *Y*(Y + 2) + 1/2*X*A *(Y + Z)
Finally, with X factored, RAT on and ALLFAC off we
retrieve the original structure
2 2 2
X *(Y + 2*Y) + X*(Y + Z)/(2*A)
3.2.4 Output of Strings
It is often useful to write a title or comment on output, or
name output expressions in a particular way. This is possible in
REDUCE by means of the command WRITE. The form of this command is
WRITE <expression>,...,<expression>;
where <expression> may be either an algebraic expression or a string
(Section 2.6). Strings are printed on output exactly as given except
for any characters which are ignored by the input scanner. Other
expressions are evaluated and their value printed.
The print line is closed at the end of the WRITE command
evaluation.
Example:
The following program calculates the famous f and g series
[1].
X1:= -SIG*(MU+2*EPS)$
X2:= EPS-2*SIG**2$
X3:= -3*MU*SIG$
F:= 1$
G:= 0$
FOR I:= 1 STEP 1 UNTIL 10 DO BEGIN
F1:= -MU*G + X1*DF(F,EPS) + X2*DF(F,SIG) + X3*DF(F,MU)$
WRITE "F(",I,") ← ",F1;
G1:= F + X1*DF(G,EPS) + X2*DF(G,SIG) + X3*DF(G,MU)$
WRITE "G(",I,") ← ",G1;
F:=F1$
G:=G1$
END;
A portion of the output, to illustrate the printout from the WRITE
command, is as follows:
... <prior output> ...
2
F(4) ← MU*(3*EPS - 15*SIG + MU)
G(4) ← 6*SIG*MU
2
F(5) ← 15*SIG*MU*( - 3*EPS + 7*SIG - MU)
2
G(5) ← MU*(9*EPS - 45*SIG + MU)
... <more output> ...
3.2.5 Suppression of Zeros
It is sometimes annoying to have zero assignments (i.e.
assignments of the form <expression> ← 0) printed, especially in
setting large arrays with many zero elements. The output from such
assignments can be suppressed by turning on the flag NERO.
3.3 User Control of the Evaluation Process
In addition to the wide range of output options available to
the user, there are two additional flags which control the internal
evaluation of expressions. The flag EXP controls expansion of
expressions. If it is off no expansion of powers or products of
expressions occurs.
When two rational functions are added, REDUCE normally
produces an expression over a common denominator. However, if the
user does not want denominators combined, he can turn off the flag
MCD which controls this process.
EXP and MCD are normally on.
3.4 Cancellation of Common Factors
Facilities are available in REDUCE for cancelling common
factors in the numerators and denominators of expressions, at the
option of the user. The system computes the required greatest common
divisor using an algorithm due to G.E. Collins [2] and cancels this
divisor from the relevant terms. This facility should only be used
on small expressions as the computational time quickly becomes
prohibitive for moderately large expressions in several variables.
The system will perform this greatest common divisor check if the
flag GCD is on.
A check is automatically made, however, for common variable
products in the numerators and denominators of expressions, and the
appropriate cancellations made.
3.5 Numerical Evaluation of Expressions
It is naturally possible to evaluate expressions numerically
in REDUCE by giving all variables and sub-expressions numerical
values. However, as we pointed out in Section 2.10.1 the user must
declare real arithmetical operation by turning on the flag FLOAT.
Furthermore, there are no routines for evaluation of the elementary
functions COS,SIN etc for arbitrary numerical argument. Finally,
arithmetic in REDUCE is not particularly fast.
The user with a large amount of numerical computation after
all necessary algebraic manipulations have been performed is
therefore well advised to perform these calculations in a FORTRAN or
similar system. For this purpose, REDUCE offers facilities for users
to produce FORTRAN compatible files for numerical processing.
First, when the flag FORT is on, the system will print
expressions in a FORTRAN notation. Expressions begin in column 7. If
an expression extends over one line, a continuation mark (X) appears
on subsequent cards. After 19 continuation lines are produced, a
new expression is started. If the expression printed arises from
an assignment to a variable, the variable is printed as the name of
the expression. Otherwise the expression is named ANS. Secondly,
the WRITE command can be used to produce other programs.
Example:
The following REDUCE statements
ON FORT;
OUT FORFIL;
WRITE "C THIS IS A FORTRAN PROGRAM";
WRITE " 1 FORMAT(E13.5)";
WRITE " U=1.23";
WRITE " V=2.17";
WRITE " W=5.2";
X←(U+V+W)↑11;
WRITE "C OF COURSE IT WAS FOOLISH
TO EXPAND THIS EXPRESSION";
WRITE " PRINT 1,X";
WRITE " END";
SHUT FORFIL;
OFF FORT;
will generate a file FORFIL which contains:
C THIS IS A FORTRAN PROGRAM
1 FORMAT(E13.5)
U=1.23
V=2.17
W=5.2
X=U**11+11*U**10*V+11*U**10*W+55*U**9*V**2+110*U**9
X*V*W+55*U**9*W**2+165*U**8*V**3+495*U**8*V**2*W+495
X*U**8*V*W**2+165*U**8*W**3+330*U**7*V**4+1320*U**7*
XV**3*W+1980*U**7*V**2*W**2+1320*U**7*V*W**3+330*U**
X7*W**4+462*U**6*V**5+2310*U**6*V**4*W+4620*U**6*V**
X3*W**2+4620*U**6*V**2*W**3+2310*U**6*V*W**4+462*U**
X6*W**5+462*U**5*V**6+2772*U**5*V**5*W+6930*U**5*V**
X4*W**2+9240*U**5*V**3*W**3+6930*U**5*V**2*W**4+2772
X*U**5*V*W**5+462*U**5*W**6+330*U**4*V**7+2310*U**4*
XV**6*W+6930*U**4*V**5*W**2+11550*U**4*V**4*W**3+
X11550*U**4*V**3*W**4+6930*U**4*V**2*W**5+2310*U**4*
XV*W**6+330*U**4*W**7+165*U**3*V**8+1320*U**3*V**7*W
X+4620*U**3*V**6*W**2+9240*U**3*V**5*W**3+11550*U**3
X*V**4*W**4+9240*U**3*V**3*W**5+4620*U**3*V**2*W**6+
X1320*U**3*V*W**7+165*U**3*W**8+55*U**2*V**9+495*U**
X2*V**8*W+1980*U**2*V**7*W**2+4620*U**2*V**6*W**3+
X6930*U**2*V**5*W**4+6930*U**2*V**4*W**5+4620*U**2*V
X**3*W**6+1980*U**2*V**2*W**7+495*U**2*V*W**8+55*U**
X2*W**9+11*U*V**10+110*U*V**9*W+495*U*V**8*W**2+1320
X*U*V**7*W**3
X=X+2310*U*V**6*W**4+2772*U*V**5*W**5+2310*U*V**4*W
X**6+1320*U*V**3*W**7+495*U*V**2*W**8+110*U*V*W**9+
X11*U*W**10+V**11+11*V**10*W+55*V**9*W**2+165*V**8*W
X**3+330*V**7*W**4+462*V**6*W**5+462*V**5*W**6+330*V
X**4*W**7+165*V**3*W**8+55*V**2*W**9+11*V*W**10+W**
X11
C OF COURSE IT WAS FOOLISH TO EXPAND THIS EXPRESSION
PRINT 1,X
END
The number of continuation cards per statement can be modified by the
assignment
!*CARDNO ← <number>;
where <number> is the TOTAL number of cards allowed in a statement.
*CARDNO is thus initially set to 20.
3.6 Saving Expressions for Later Use as Input
It is often useful to save an expression on an external file
for use later as input in further calculations. The commands for
opening and closing output files were explained in Section 2.13.
However, we see in the examples in Section 3.2 that the standard
`natural' method of printing expressions in not compatible with the
input syntax. So to print the expression in an input compatible
form we must inhibit this natural style by turning off the flag NAT.
If this is done, a dollar sign will also be printed at the end of the
expression.
Example:
The following program
OFF NAT;
OUT OUT;
X←(Y+Z)↑2;
WRITE "END;";
SHUT OUT;
ON NAT;
will generate a file OUT which contains
X := Y**2 + 2*Y*Z + Z**2
$
END;
3.7 Partitioning Expressions
It is often necessary to get at parts of an expression during
a calculation. REDUCE provides four commands for this purpose, each
of which apply to the current expression in the work space. These
have proved adequate for all calculations brought to the author's
attention, but other commands could be added if there is sufficient
demand.
(1) MKCOEFF is a command which assigns coefficients of the
various powers of a variable. It has the syntax:
MKCOEFF <variable>,<identifier>;
If the <identifier> has been previously declared a single
dimensioned array, the Ith array element is assigned to the
coefficient (zero or non zero) of the Ith power of <variable> in the
expression. This assignment begins at the maximum power of the
variable, and a message is printed to inform the user of that power.
If the <identifier> is not an array name, a variable with
name <identifier><power> is assigned to the coefficient of that
power. Only NON ZERO powers are set in this manner, and a message is
printed to inform the user of the variables set.
Example:
Suppose we evaluate the expression (Y↑2+Z)↑3, so that the
workspace holds the expression
Y↑6 + 3*Y↑4*Z + 3*Y↑2*Z↑2 + Z↑3
If we now say ARRAY X(7); MKCOEFF Y,X;
then a message
HIGHEST POWER IS 6
will be printed and X(6) set to 1, X(5) to 0, X(4) to 3*Z and so on
until X(0), which is set to Z↑3. X(7) will not be set.
On the other hand, if we said MKCOEFF Y,W;
we would get a message
W6 W4 W2 W0 ARE NON ZERO
and W6 set to 1, W4 to 3*Z and so on.
(2) NUMER and DENOM are commands which have a single variable
argument and which respectively assign the numerator and denominator
of the workspace to their argument.
e. g., with X/Y↑2 in the workspace,
NUMER V; will set V to X, and DENOM W; will set W to Y↑2.
(3) ND, finally, takes two variables as argument, and assigns the
numerator of the workspace to the first, and the denominator to the
second.
e. g., we could achieve the assignments in (2) with the
single command ND V,W;
%TOP,,,,4-1
4. MATRIX CALCULATIONS
4.1 Preliminary
A very powerful feature of the REDUCE system is the ease with
which matrix calculations can be performed. To extend our syntax to
this class of calculations we need to add another prefix operator,
MAT, and a further variable and expression type as follows:
4.2 MAT
This prefix operator is used to represent n x m matrices. MAT
has n arguments interpreted as rows of the matrix, each of which is a
list of m expressions representing elements in that row. For example,
the matrix
| A B C |
| |
| D E F |
would be written as
MAT ((A,B,C),(D,E,F))
4.3 Matrix variables.
An identifier may be declared a matrix variable by the
declaration MATRIX. Matrices are stored as arrays in REDUCE. The
size of the matrix may be declared explicitly in the matrix
declaration, or by default in assigning such a variable to a matrix
expression.
e. g. MATRIX X(2),Y(3,4),Z;
declares X to be a 2 x 1 (column) matrix, Y to be a 3 x 4 matrix and
Z a matrix whose size is declared later by default.
4.4 Matrix Expressions
These follow the normal rules of matrix algebra as defined by
the following syntax:
<matrix expression> ::= MAT<matrix description>|<matrix variable>|
<scalar expression>*<matrix expression>|
<matrix expression>*<matrix expression>
<matrix expression>+<matrix expression>|
<matrix expression>↑<integer>|
<matrix expression>/<matrix expression>
Sums and products of matrix expressions must have the same
size otherwise an error will result during their evaluation.
Similarly, only square matrices may be raised to a power. A negative
power is computed as the inverse of the matrix raised to the
corresponding positive power. A/B is interpreted as AxB↑(-1).
The inverse of a matrix is computed by an algorithm due to
John Lipson [3]. I am indebted to Dr. Jim Griesmer for allowing me to
include in REDUCE his programmed version of this algorithm.
Examples:
Assuming X and Y have been declared as matrices, the
following are matrix expressions
Y
Y↑2*X-3*Y↑(-2)*X
Y+ MAT((1,A),(B,C))/2
4.5 Operators With Matrix Arguments
Two additional operators are useful in matrix calculations,
namely DET and TRACE defined as follows
4.5.1 DET
The operator DET is used to represent the determinant of a
square matrix expression.
e.g. DET(Y↑2)
is a scalar expression whose value is the determinant of the square
of the matrix Y. The particular construction
DET(MAT <matrix description>) max be abbreviated to
DET<matrix description>
For example, the determinant
| A B C |
| |
| D E F |
| |
| G H J |
could be written
DET((A,B,C),(D,E,F),(G,H,J));
4.5.2 TRACE
The operator TRACE is used to represent the trace of a square
matrix. Its use is obvious.
4.6 Matrix Assignments
Matrix expressions may appear in the right hand side of
assignment statements. If the left hand side of the assignment, which
must be a variable, has not already been declared a matrix, it is
declared by default to the size of the right hand side. The variable
is then set to the value of the right hand side.
Such an assignment may be used very conveniently to find the
solution of a set of linear equations. For example, to find the
solution of the following set of equations
A11*X(1) + A12*X(2) = Y1
A21*X(1) + A22*X(2) = Y2
we simply write
X ← 1/MAT((A11,A12),(A21,A22))*MAT((Y1),(Y2));
4.7 Evaluating Matrix Elements
Once an element of a matrix has been assigned, it may be
referred to in standard array element notation. Thus Y(2,1) refers
to the element in the second row and first column of the matrix Y.
%TOP,,,,5-1
5. ADVANCED COMMANDS
In this Section, we consider several extensions of the basic
REDUCE system which add to its power as a problem solving tool.
We begin by introducing a new data type which is needed to
extend our syntax, namely the kernel.
5.1 Kernels
REDUCE is designed so that each operator in the system has a
evaluation (or simplification) function associated with it which
transforms the expression into an internal canonical form. This form,
which bears little resemblance to the original expression, is
described in detail in Reference [4].
The evaluation function may transform its arguments in one
of two alternative ways. First, it may convert the expression into
other operators in the system, leaving no functions of the original
operator for further manipulation. This is in a sense true of the
evaluation functions associated with the operators +, * and / , for
example, because the canonical form does not include these operators
explicitly. It is also true of an operator such as the determinant
operator DET discussed in Section 4.5.1, because the relevant
evaluation function calculates the appropriate determinant, and the
operator DET no longer appears. On the other hand, the evaluation
process may leave some residual functions of the relevant operator.
For example, with the operator COS, a residual expression like COS(X)
may remain after evaluation unless a rule for the reduction of
cosines into exponentials, for example, were introduced. These
residual functions of an operator are termed kernels and are stored
uniquely like variables. Subsequently, the kernel is carried through
the calculation as a variable unless transformations are introduced
for the operator at a later stage.
In cases where the arguments of the kernel operators may be
reordered, the system puts them in a canonical order, based on an
internal intrinsic ordering of the variables. However, some
commands allow arguments in the form of kernels, and the user has no
way of telling what internal order the system will assign to these
arguments. To resolve this difficulty, we introduce the notion of
a kernel form as an expression which transforms to a kernel on
evaluation.
Examples of kernel forms are:
A
COS (X*Y)
LOG (SIN (X))
whereas
A*B
(A+B)↑4
are not.
We see that kernel forms are in fact the 'functional expressions'
previously allowed in LET and FACTOR statements.
5.2 Substitutions for General Expressions
All substitutions discussed so far have been very limited in
scope, because they involve only replacements for variables and
kernels. These substitutions are very efficient to implement because
variables and kernels are stored uniquely in the system. However,
there are many situations where more general substitutions are
required, most of which require extensive pattern matching within the
expression being evaluated . Consequently, such substitutions cannot
be as efficiently implemented as those discussed so far.
For the reasons given in References [5] and [6], REDUCE does
not attempt to implement a general pattern matching algorithm.
However, the present system uses more sophisticated techniques than
those discussed in reference [6]. It is now possible for the
equations appearing in arguments of LET to have the form
<substitution expression> = <expression>
where <substitution expression> is ANY expression, subject to the
following restrictions:
(i) The operators +, - and / cannot appear at the top level in a
substitution expression. This restriction is currently under
study to see if it can be removed.
e. g. LET COS(X)↑2 + SIN(X)↑2 = 1; is NOT allowed.
(ii) The operators + and * can only be used in binary form within
substitution expressions.
e. g. LET SIN (X + Y) = SIN(X)*COS(Y) + COS(X)*SIN(Y);
is allowed but a substitution for FN(X+Y+Z) would not be. The
system will of course substitute for any expression containing +
or * as an n-ary operator by making the appropriate expansion of
the binary rule.
(iii) The operator - can only be specified as a unary operator within
substitution expressions.
e. g. LET COS(-X)= COS(X) is allowed
but LET COS(X-Y) = <expression> is not.
It should be noted, however, that a rule for COS(X+Y) and one
for COS(-X) is sufficient to specify the expansion of COS(X-Y).
Any variables appearing in substitution expressions may be
declared arbitrary by the FOR ALL construction
e. g. FOR ALL X,Y LET COS(X+Y)=COS(X)*COS(Y)-SIN(X)*SIN(Y);
FOR ALL X LET LOG(E↑X) = X, E↑LOG(X)= X,
COS(W*T+THETA(X)) = TAU(X);
It is also possible to limit the range of an arbitrary
variable by an extension of the syntax of the IF statement. The
relevant form is
IF <boolean expression> LET <substitution list>
To include completely arbitrary variables in this syntax, we use the
boolean operator ARB rather than combine the IF construction with a
FOR ALL clause.
e. g. IF X ≠ 0 ∧ NUMBERP N ∧ ARB Y LET F(X,Y,N)= 2*Y↑N;
As before, after a substitution has been made, the expression
being evaluated is reexamined in case a new allowed substitution has
been generated. This process is continued until no more substitutions
can be made. However, this is sometimes undesirable. For example,
if one wishes to integrate a polynomial with respect to X by a rule
of the form
FOR ALL N LET X↑N = X↑(N+1)/(N+1);
one only wants the substitution to be made once. (Otherwise X↑2 would
become X↑3/3 which would then become X↑4/12 and so on). This
resubstitution can be inhibited by turning off the flag RESUBS (which
is normally on).
When a substitution expression appears in a product, the
substitution is made if that expression divides the product. For
example, the rule
LET A↑2*C = 3*Z;
would cause A↑2*C*X to be replaced by 3*Z*X and A↑2*C↑2 by 3*Z*C. If
the substitution is desired only when the substitution expression
appears in a product with the explicit powers supplied in the rule,
the command MATCH should be used instead.
For example,
MATCH A↑2*C = 3*Z;
would cause A↑2*C*X to be replaced by 3*Z*X, but A↑2*C↑2 would not be
replaced. MATCH can also be used with the FOR ALL or IF constructions
described above.
To remove substitution rules of the type discussed in this
Section, the CLEAR command can be used, combined, if necessary, with
a FOR ALL or IF clause.
e.g. FOR ALL X CLEAR LOG(E↑X), E↑LOG(X), COS(W*T+THETA(X));
Note, however, that the arbitrary variable names in this case MUST be
the same as those used in defining the substitution.
5.3 Asymptotic Commands
In expansions of polynomials involving variables which are
known to be small, it is often desirable to throw away all powers of
these variables beyond a certain point to avoid unnecessary
computation. The command LET may be used to do this. For example,
if only powers of X up to X↑7 are needed, the command
LET X↑8 = 0;
will cause the system to delete all powers of X higher than 7.
This method is not adequate, however, when expressions
involve several variables having different degrees of smallness.
In this case, it is necessary to supply an asymptotic weight to each
variable and count up the total weight of each product in an expanded
expression before deciding whether to keep the term or not. There
are two associated commands in the system to permit this type of
asymptotic constraint. The command WEIGHT takes a list of equations
of the form
<kernel form> = <number>,
where <number> must be a positive integer. This command assigns the
weight <number> to the relevant kernel form. A check is then made in
all algebraic evaluations to see if the total weight of the term is
equal to or greater than the weight level assigned to the
calculation. If it is, the term is deleted. To compute the total
weight of a product, the individual weights of each kernel form are
multiplied by their corresponding powers and then added.
The weight level of the system is initially set to 2. The
user may change this setting, however, by the command
WTLEVEL <number>;
which sets <number> as the new weight level of the system. Again,
<number> must be a positive integer.
Restrictions:
In the present system, it is not possible to differentiate
with respect to a variable for which a weight has been assigned,
or for such a variable to appear in a substitution expression. These
restrictions could be removed if they prove too inconvenient for
users.
%TOP,,,,6-1
6. SYMBOLIC MODE
6.1 Preliminary
Although REDUCE is designed primarily for algebraic
calculations, its source language is general enough to allow for a
full range of LISP-like symbolic calculations. To achieve this
generality, however, it is necessary to provide the user with two
modes of evaluation, namely an algebraic mode and a symbolic mode. To
enter symbolic mode, the user types LISP; (or SYMBOLIC;) and to
return to algebraic mode he types ALGEBRAIC;. Evaluations proceed
differently in each mode so the user is advised to check what mode he
is in if a puzzling error arises. He can find his mode by typing
!*MODE;
The current mode will then be printed as ALGEBRAIC or SYMBOLIC.
If you wish to enter the other mode for a limited time, it is
possible to say
LISP <command> (or SYMBOLIC <command>)
or ALGEBRAIC <command>
At the end of the evaluation, you will be back in the previous mode.
For example, if the current mode is ALGEBRAIC, then the commands
LISP CAR '(A);
X+Y;
will be evaluated in symbolic mode and algebraic mode respectively.
This section assumes that the reader has a reasonable
acquaintance with LISP 1.5 at the level of the LISP 1.5 Programmer's
Manual [7] or Clark Weissman's LISP 1.5 Primer[8]. Persons unfamiliar
with this material will have some difficulty understanding this
Section!
Except where explicit limitations have been made, most REDUCE
algebraic constructions carry over into symbolic mode. However,
there are two major differences. First, expression evaluation now
becomes LISP evaluation. Secondly, assignment statements are handled
differently. We shall describe this difference later. In addition,
function definitions follow the conventions of Standard LISP [9].
To begin with, we mention a few extensions to our basic
syntax which are designed primarily if not exclusively for symbolic
mode.
6.2 General Identifiers
In Section 2.3, we limited identifiers to sequences of
letters and numbers. However, it is possible to input any sequence
of characters in REDUCE as a name by prefixing non alphanumeric
characters by the 'escape character' ! .
e.g. A!(B is an allowed identifier. It will print as A(B.
6.3 Symbolic Infix Operators
There are three binary infix operators in REDUCE intended for
use in symbolic mode. These operators and their alphanumeric
equivalents are as follows:
ε MEMBER
≡ EQ
. CONS
The precedence of these operators is as given by the following list,
from outermost to innermost operations:
<infix operator> ::= ←|∧|∨|¬|ε|=|≠|≡|>=|>|<=|<|+|-|*|/|↑|.
6.4 Symbolic Expressions
These consist of scalar variables and operators and follow
the normal rules of the LISP meta language.
Examples:
X
CAR U . REVERSE V
SIMP (U+V↑2)
6.5 Quoted Expressions
Because LISP evaluation requires that each variable or
expression have a value, it is necessary to add to REDUCE the concept
of a quoted expression by analogy with the LISP QUOTE function. This
is provided by the single quote mark '.
e. g. 'A represents the LISP S-expression (QUOTE A)
'(A B C) represents the LISP S-expression (QUOTE (A B C))
Note, however, that strings are automatically quoted in
symbolic mode. Thus, to print the string "A STRING", one would write
PRINC "A STRING";
BEWARE!!! Within a quoted expression, normal LISP S-expression
syntax rules apply. Thus the escape character ! is just another LISP
character, as are the terminators ; and $. For example, 'A;
represents the S-expression (QUOTE A;), so you must put a space
before the semicolon if it is to act as a terminator.
6.6 LAMBDA Expressions
LAMBDA expressions provide the means for constructing LISP
LAMBDA expressions in symbolic mode. They may not be used in
algebraic mode.
Syntax:
<LAMBDA expression> ::= LAMBDA <varlist><terminator><statement>
<varlist> ::= (<variable>,...,<variable>)
e. g. LAMBDA (X,Y); CAR X . CDR Y
is equivalent to the LISP LAMBDA expression
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
The parentheses may be omitted in specifying the variable
list if desired, and λ may be used in place of the reserved word
LAMBDA.
LAMBDA expressions may be used in symbolic mode in place of
prefix operators, or as an argument of the reserved word FUNCTION,
which is used in the same way as FUNCTION in Standard LISP.
6.7 Symbolic Assignment Statements
In symbolic mode, if the left side of an assignment statement
is a variable, a SETQ of the right hand side to that variable occurs.
If the left hand side is an expression, a function definition is
assumed.
e. g. X←Y translates into (SETQ X Y)
whereas
ASSOC(U,V) ← IF NULL V THEN NIL
ELSE IF U≡ CAAR V THEN CAR V
ELSE ASSOC (U,CDR V)
defines the LISP function ASSOC.
MACROs and FEXPRs may be defined by prefixing the assignment
by the word MACRO or FEXPR.
e. g. we could define a MACRO CONSCONS by
MACRO CONSCONS L ← EXPAND(CDR L, 'CONS);
Function definitions may also be input in the procedural form
discussed in Section 2.17. The procedural type in this case is LISP
(or SYMBOLIC). For example, the above definition of ASSOC could be
written as
LISP PROCEDURE ASSOC(U,V);
IF NULL V THEN NIL
ELSE IF U≡ CAAR V THEN CAR V
ELSE ASSOC (U, CDR V);
FEXPRs and MACROS may also be input in this manner with the
procedural types FEXPR and MACRO respectively.
6.8 Communication with Algebraic Mode
If a function is defined in symbolic mode for use as an
operator in an algebraic calculation, it is necessary to communicate
this to the algebraic processor. This can be done by using the
command OPERATOR. Thus
OPERATOR FUN1,FUN2;
would declare the functions FUN1 and FUN2 as algebraic operators.
This declaration MUST be made in symbolic mode, as the effect in
algebraic mode is different.
Furthermore, if you wish to use the algebraic evaluator on an
argument in a symbolic mode definition, the function REVAL can be
used. The one argument of REVAL must be the LISP prefix equivalent
of a scalar expression, e. g., (COS (PLUS X Y)). REVAL returns the
evaluated expression in a similar form.
%TOP,,,,A-1
APPENDIX A
SUMMARY OF THE REDUCE SYSTEM
A.1 Reserved Identifiers
We list here all identifiers which are normally reserved in
REDUCE. We include in this list all reserved identifiers given in
Section 2 plus all command names and operators initially in the
system. The reserved identifiers used in high energy physics
calculations (Appendix C) are also included for completeness.
Reserved Words BEGIN DO ELSE END FOR FUNCTION IF LAMBDA NIL
PRODUCT RETURN STEP SUM UNTIL WHILE
Reserved Scalar E I
Variables
Infix Operators ← := ∧ ∨ ¬ ε = ≠ ≡ >= > <= < + - * / ↑ ** .
SETQ AND OR NOT MEMBER EQUAL UNEQ EQ GREATEQ
GREATERP LESSEQ LESSP PLUS MINUS TIMES
QUOTIENT EXPT CONS
Prefix Operators DET DF COS EPS G LOG MAT SIN SUB TRACE
Commands ALGEBRAIC ARRAY CLEAR COMMENT DENOM END
FACTOR FOR FORALL GOTO IF IN INFIX INTEGER
LET LISP MASS MATCH MATRIX MKCOEFF MSHELL ND
NOSPUR NUMER OFF ON OPERATOR ORDER OUT
PRECEDENCE PROCEDURE REAL REDUCE RETURN
SAVEAS SCALAR SHUT SPUR SYMBOLIC VECTOR
WEIGHT WRITE WTLEVEL
A.2 Commands Normally Available In REDUCE
Notation: E, E1,...,En denote expressions
V,V1,...,Vn denote variables
The number after the description refers to the Section in which the
command is described.
ALGEBRAIC E; If E is empty, the system mode is set to
algebraic. Otherwise, E is evaluated in
algebraic mode and the system mode is not
changed (6.1)
ARRAY V1<size>, Declares V1 through Vn as array names. <size>
,...,Vn<size>; describes the maximum size of the array
(2.11.2)
CLEAR E1,...En; Removes any substitutions declared for E1
through En from system (2.15)
COMMENT <any>; Used for including comments in text. <any> is
any sequence of characters not including a
terminator (2.7)
CONT; An interactive command which causes the
system to continue the calculation from the
point in the input file where the last PAUSE
was encountered (2.18)
DENOM V; Assigns V to denominator of the workspace
(3.7)
END <any>; Terminates files used for input to REDUCE.
<any> is any sequence of symbols not
including a terminator or the reserved words
END, ELSE or UNTIL (2.19)
FACTOR E1,...En; Declares expressions as factors in output
(3.2.2)
FOR Command used to define a variety of program
loops (2.10.3)
FORALL V1,...,Vn Declares variables V1 through Vn as arbitrary
<command> in the substitution rules given by <command>
(2.14, 2.16, 3.1 and 5.2)
GOTO V; Performs an unconditional transfer to label
V. Can only be used in compound statements
(2.10.4)
IF Used to define conditional statements (2.10.2
and 5.2)
IN V1,...,Vn; Inputs the external REDUCE files V1 through
Vn (2.13.1)
INFIX V1,...,Vn; Declares the non-alphanumeric characters V1
through Vn as infix operators (2.5)
INTEGER V1,...,Vn; Declares V1 through Vn as integer variables
(2.11.1)
LET E1,...,En; Declares substitutions for the left hand
sides of expressions E1 through En. (2.14 and
5.2). In addition, LET can be used to input
differentiation rules (2.16)
LISP E; If E is empty, the system evaluation mode is
set to symbolic. Otherwise, E is evaluated
in symbolic mode and the system mode not
changed (6.1)
MATCH E1,...,En; Declares substitutions for the left hand
sides of E1 through En when matching of
explicit powers is required (5.2)
MATRIX E1,...,En; Declares matrix variables to the system. The
Ei may be matrix variable names, or include
details of the size of the matrix (4.3)
MKCOEFF V1,V2; Used to partition expression in the
workspace. The various powers of V1 in this
expression are stored in V2 (3.7)
ND V1,V2; Assigns V1 to numerator of the workspace and
V2 to its denominator (3.7)
NUMER V; Assigns V to numerator of the workspace (3.7)
OFF V1,...,Vn; Turns off the flags V1 through Vn (2.11.3)
ON V1,...,Vn; Turns on the flags V1 through Vn (2.11.3)
OPERATOR V1,...,Vn; Declares V1 through Vn as algebraic operators
(2.5 and 6.8)
ORDER V1,...,Vn; Declares an ordering for variables V1 through
Vn on output (3.2.1)
OUT V; Declares V as output file (2.13.2)
PAUSE; An interactive command for use in an input
file. When it is evaluated, control is
transferred to the user's terminal (2.18)
PRECEDENCE V1,V2; Gives infix operator V1 a new precedence
immediately higher than the current
precedence of V2 (2.5)
PROCEDURE Names a statement for repeated use in
calculations. Type specification of procedure
precedes the command name (2.17 and 6.7)
REAL V1,...,Vn; Declares variables V1 through Vn as real
(2.11.1)
RETURN E; Causes a transfer out of a compound statement
to the next highest program level. Value of E
is returned from compound statement. E may be
empty (2.10.6)
SAVEAS E; Assigns E to the current expression in the
workspace (3.1)
SCALAR V1,...,Vn; Declares variables V1 through Vn as scalar
(2.11.1)
SHUT V; Closes the output file V (2.13.3)
SYMBOLIC E; Same as LISP E;
WEIGHT E1,...En; Assigns an asymptotic weight to the left hand
sides of E1 through En (5.3)
WRITE E1,...,En; Causes the values of E1 through En to be
written on the current output file (3.2.4)
WTLEVEL V; Sets the asymptotic weight level of the
system to V (5.3)
A.3 Mode Flags in REDUCE
This Section lists the flags which may appear as arguments of
ON and OFF. The action of the flag when it is ON is described here,
unless stated otherwise. The numbers, as previously, refer to the
Section in which the flag is described.
ALLFAC Causes the system to factor out common products on
output of expressions (3.2.3)
DIV Causes the system to divide out simple factors on
output, so that negative powers or rational fractions
can be produced (3.2.3)
ECHO Causes echoing of input (2.13.1)
EXP Causes expressions to be expanded during evaluation
(3.3)
FLOAT Prevents conversion of floating point numbers into
the ratio of two integers during evaluation (2.10.1)
FORT Declares output in a FORTRAN notation (3.5)
GCD Causes the system to cancel greatest common divisors
in rational expressions (3.4)
INT Specifies an interactive mode of operation (2.18)
LIST Causes output to be listed one term to a line (3.2.3)
MCD Causes denominators to be combined when expressions
are added (3.3)
MSG Causes diagnostic messages to be printed (2.14)
NAT Specifies 'natural' style of output (3.6)
NERO Inhibits printing of zero assignments (3.2.5)
RAT An output flag used in conjunction with FACTOR. It
causes the overall denominator in an expression to
be printed with each factored sub-expression (3.2.3)
RESUBS When RESUBS is OFF, the system does not reexamine an
expression for further substitutions after one has
been made (5.2)
A.4 Diagnostic and Error Messages in REDUCE
Diagnostic messages in the REDUCE system are of two types;
error messages and warning messages. The former usually cause the
termination of the current calculation whereas the latter warn the
user of an ambiguity encountered or some action taken which may
indicate an error. If the system is in an interactive state, it can
ask the user when it encounters an ambiguity for the correct
interpretation. Otherwise it will make the most plausible guess,
print a message informing the user of the choice made, and continue.
If an error is found during the parsing of the input, the
current phrase is reprinted with the place marked where the error was
encountered. In some systems, it is then possible to edit the line
and correct the error.
For completeness, again, we include messages which can occur
in High Energy Physics calculations (Appendix C).
A.4.1 Error Messages
ARRAY TOO SMALL An array used in MKCOEFF is too small to
store all powers of the expression being
partitioned
ASSIGNMENT <expression> An invalid assignment has been input to the
NOT ALLOWED system
FORMAT <expression> The format of the argument of a command is
INCORRECT incorrect
INCORRECT ARRAY Non-numeric index has been used with matrix
ARGUMENTS FOR <name> <name>
INVALID CHARACTER Invalid character found on input
MATRIX MISMATCH Two matrix expressions are not correctly
matched for addition or multiplication
MATRIX SYNTAX A syntax error has been encountered in a
matrix expression
MISMATCH OF ARGUMENTS Indicates that an operator for which an
evaluation procedure has been defined is
called with the wrong number of arguments
MISSING OPERATOR Input error
MISSING VECTOR An expression encountered in a vector context
does not contain a vector
NON SQUARE MATRIX An invalid operation on a non square matrix
has been requested (e. g., a trace)
REDUNDANT OPERATOR Input error
SINGULAR MATRIX System has been asked to invert a singular
matrix
SUB FORMAT The arguments of the operator SUB have the
wrong format
SYNTAX ERROR Incorrect syntax in input. This error occurs
only if the system is unable to determine
what causes the error
TOO FEW RIGHT Input error
PARENTHESES
TOO MANY RIGHT Input error
PARENTHESES
UNMATCHED INDEX Unmatched indices have been encountered during
ERROR <list> the evaluation of a vector expression
VECTOR <variable> A vector variable has been used in a scalar
USED AS SCALAR context
ZERO DENOMINATOR An expression with a zero denominator has
been encountered
<operator> NOT FOUND An unknown operator appears in a PRECEDENCE
declaration
<variable> INVALID IN Incorrect statement syntax
<statement name> STATEMENT
<variable> HAS NO MASS A variable encountered in an MSHELL
declaration has no mass assigned to it
A.4.2 Diagnostic Messages
ASSIGNMENT FOR <expression> <expression> has been reassigned to a
REDEFINED new value
<expression> REPRESENTED The system has represented the first
BY <expression> expression by the second
<expression> NOT FACTORABLE An invalid expression has been given
<variable> DECLARED <type> <variable> has been declared <type>
%TOP,,,,B-1
APPENDIX B
B.1 RUNNING REDUCE ON THE STANFORD PDP-10
B.1.1 REDUCE is stored as a 38K system with filename REDUCE.DMP.
The complete source program, written in REDUCE, is stored in the user
area [1,ACH] with filename REDUCE.RED if anyone is interested in
studying it.
REDUCE may be loaded by typing R REDUCE. When the system
returns an asterisk, you are in LISP. You can then enter REDUCE by
typing (BEGIN). The system then expects REDUCE commands from you.
You can return to LISP by the command END;
If you require more core for your job, you can get it by
typing
↑C
.CORE <size required><cr>
.REE<cr>
You will then be back in LISP.
B.1.2 Special Features
B.1.2.1 If you give IN and OUT a variable or dotted pair as argument,
the output goes to your disk area. In addition, the reserved
identifier L is used to represent the line printer on output.
i. e. OUT L;
sends output to the line printer.
Input from other devices may be specified by preceding the
file name by the device name. For example, to input a file ANDY from
disk area [S,JAM] followed by FOO from DTA2:, you would type
IN (S,JAM),ANDY,DTA2!:,FOO;
B.1.2.2 The altmode character may be used as a terminator. However,
if it is used, no results are printed when expressions are evaluated;
the semicolon must be used in this case.
B.1.3 A SAMPLE PROGRAM
.R REDUCE load the program
*(BEGIN) enter REDUCE
*COMMENT A SAMPLE PROGRAM; comments are allowed
*X←(Y+Z)↑2; set X to (Y+Z)↑2
2 2 here's the result printed
X := Y + 2*Y*Z + Z because we used a semicolon
as a terminator
*DF(X,Z,2); now differentiate X wrt Z twice
2 here's that result
*PROCEDURE FAC N; now define the factorial
* BEGIN INTEGER M,N; function
* M←1;
* A: IF N=0 THEN RETURN M;
* M←M*N;
* N←N-1;
* GO TO A
* END;
*2↑FAC 3; we can omit the parentheses
64
*FAC (120); or put them in with unary
operators
<yes. big numbers do work!>
*COMMENT THE FOLLOWING IS USEFUL ONLY IF YOU ARE
INTERESTED IN SYMBOLIC MODE;
*LISP; enter symbolic mode
NIL value returned in symbolic mode
*CAR ('(A)); compute the CAR of (A)
A here's its value
*ASSOC(U,V)←IF NULL V THEN NIL now define ASSOC
* ELSE IF U≡ CAAR V THEN CAR V
* ELSE ASSOC(U,CDR V);
*** ASSOC REDEFINED REDUCE diagnostic message
ASSOC value from ASSOC definition
*ASSOC ('A,'((B . C) (A . D))); test ASSOC
(A . D) it works!
*END; return to LISP
*** value of END routine
"ENTERING LISP..." so that you know
*
B.2 RUNNING REDUCE ON THE STANFORD CAMPUS FACILITY IBM 360/67
Instructions for running REDUCE on this machine are
obtainable from the AIDS Office in Pine Hall.
%TOP,,,,C-1
APPENDIX C
CALCULATIONS IN HIGH ENERGY PHYSICS
C.1 Preliminary.
A set of REDUCE commands is provided for users interested in
symbolic calculations in high energy physics. Several extensions to
our basic syntax are necessary, however, to allow for the more
complicated data structures encountered.
C.2 Operators used in High Energy Physics Calculations.
We begin by introducing three new operators required in these
calculations.
C.2.1 .
The . operator is a binary operator used in algebraic mode
to denote the scalar product of two Loretz four-vectors. In the
present system, the index handling routines all assume that Lorentz
four-vectors are used, but these routines could be rewritten to
handle other cases.
Components of vectors can be represented by including
representations of unit vectors in the system. Thus if EO represents
the unit vector (1,0,0,0), (P.EO) represents the zeroth component of
the four-vector P. Our metric and notation follows Bjorken and
Drell[10]. Similarly, an arbitrary component P may be represented
by (P.U). If contraction over components of vectors is required,
then the declaration INDEX must be used.
Thus
INDEX U;
declares U as an index, and the simplification of
(P.U) * (Q.U)
would result in
(P.Q)
The metric tensor g may be represented by (U.V). If
contraction over u and v is required, then U and V should be declared
as indices.
The declaration REMIND V1...VN $ removes the index flags from
the variables V1 through VN. However, these variables remain vectors
in the system.
C.2.2 G
G is an n-ary operator used to denote a product of gamma
matrices contracted with Lorentz four-vectors. Gamma matrices are
associated with fermion lines in a Feynman diagram. If more than one
such line occurs, then a different set of gamma matrices (operating
in independent spin spaces) is required to represent each line. To
facilitate this, the first argument of G is a line identification
identifier (not a number) used to distinguish different lines.
Thus
G(L1,P) * G(L2,Q)
denotes the product of P associated with a fermion line identified as
L1, and Q associated with another line identified as L2 and where P
and Q are Lorentz four-vectors. A product of gamma matrices
associated with the same line may be written in a contracted form.
Thus
G(L1,P1,P2,...,P3) ≡ G(L1,P1)*G(L1,P2)*,...,*G(L1,P3)
The vector A is reserved in arguments of G to denote the special
gamma matrix .
Thus
G(L,A) ≡ associated with line L.
G(L,P,A) ≡ associated with line L.
(associated with line L) may be written as G(L,U), with U flagged
as an index if contraction over u is required.
The notation of Bjorken and Drell [10] is assumed in all
operations involving gamma matrices.
C.2.3 EPS
The operator EPS has four arguments, and is used only to
denote the completely antisymmetric tensor of order 4 and its
contraction with Lorentz four-vectors.
Thus
ε = { +1 if α,β,u,v is an even permutation of 0,1,2,3
αβuv { -1 if an odd permutation
{ 0 otherwise
A contraction of the form ε p q may be written as EPS(AL,BE,P,Q),
αβuv u v
with AL and BE flagged as indices, and so on.
C.3 Vector variables.
Apart from the line identification identifier in the G
operator, all other arguments of the operators in Section B.2 are
vectors. Variables used as such must be declared so by the type
declaration VECTOR.
e. g. VECTOR P1,P2;
declares P1 and P2 to be vectors. Variables declared as indices or
given a mass (Section C.6) are automatically declared vector by these
declarations.
C.4 Additional Expression Types.
Two additional expression types are necessary for high energy
calculations, namely
C.4.1 Vector Expressions.
These follow the normal rules of vector combination. Thus
the product of a scalar or numerical expression and a vector
expression is a vector, as are the sum and difference of vector
expressions. If these rules are not followed, error messages are
printed. Furthermore, if the system finds an undeclared variable
where it expects a vector variable, it will ask the user in
interactive mode whether to make that variable a vector or not. In
batch mode, the declaration will be made automatically and the user
informed of this by a message.
Examples:
Assuming P and Q have been declared vectors, the following
are vector expressions
P
P-2*Q/3
2*X*Y*P - P.Q*Q/(3*Q.Q)
whereas P*Q and P/Q are not.
C.4.2 Dirac Expressions
These denote those expressions which involve gamma matrices.
A gamma matrix is implicitly a 4 x 4 matrix, and so the product, sum
and difference of such expressions, or the product of a scalar and
Dirac expression is again a Dirac expression. There are no Dirac
variables in the system, so whenever a scalar variable appears in a
Dirac expression without an associated gamma matrix expression, an
implicit unit 4 x 4 matrix is assumed.
e. g. G(L,P) + M denotes G(L,P) + M*<unit 4 x 4 matrix>
Multiplication of Dirac expressions, as for matrix
expressions, is of course non-commutative.
C.5 Trace Calculations.
When a Dirac expression is evaluated, the system computes one
quarter of the trace of each gamma matrix product in the expansion of
the expression. One quarter of each trace is taken in order to avoid
confusion between the trace of the scalar M, say, and M representing
M * <unit 4 x 4 matrix>.
The algorithms used for trace calculations are the best
available at the time this system was produced. For example, in
addition to the algorithm developed by Chisholm [11] for contracting
indices in products of traces, REDUCE uses the elegant algorithm of
Kahane [12] for contracting indices in gamma matrix products.
It is possible to prevent the trace calculation over any line
identifier by the declaration NOSPUR.
e. g. NOSPUR L1,L2;
will mean that no traces are taken of of gamma matrix terms involving
the line numbers L1 and L2. Furthermore, any product of gamma
matrices may be reduced to combinations of the sixteen fundamental
gamma matrices by the declaration REDUCE.
e. g. REDUCE L1,L2;
will mean that products of gamma matrices with line numbers L1 and L2
will be reduced to the sixteen fundamental forms. The declaration
REDUCE naturally includes NOSPUR. This command should be used with
extreme caution. For example, the reduction of a product of six
different 'slashed' vectors generates 66 terms!
A trace of a gamma matrix expression involving a line
identifier which has been declared NOSPUR or REDUCE may be later
taken by making the declaration SPUR. SPUR cancels both NOSPUR and
REDUCE.
C.6 Mass Declarations
It is often necessary to put a particle 'on the mass shell'
in a calculation. This can, of course, be accomplished with a LET
command such as
LET P.P= M↑2;
but an alternative method is provided by two commands MASS and
MSHELL. MASS takes a list of equations of the form:
<vector variable> = <scalar variable>
e. g. MASS P1=M, Q1=MU;
The only effect of this command is to associate the relevant scalar
variable as a mass with the corresponding vector. If we now say
MSHELL <vector variable>,...,<vector variable>;
and a mass has been associated with these arguments, a substitution
of the form
<vector variable>.<vector variable> = <mass>↑2
is set up. An example of this is given in the following.
C.7 Example
We give here as an example of a simple calculation in high
energy physics the computation of the Compton scattering
cross-section as given in Bjorken and Drell[10], Eqs. (7.72)
through(7.74).
We wish to compute
2 2 pf+m ε'εki + εε'kf pi+m kiεε' + kfε'ε
α /2 (k'/k) trace {(----)(----- ------)(----)(----- ------)}
2m 2k.pi 2k'.pi 2m 2k.pi 2k'.pi
where ki and kf are the four-momenta of incoming and outgoing photons
(with polarization vectors ε and ε' and laboratory energies k and k'
respectively) and pi,pf are incident and final electron four-momenta.
Omitting the factor α↑2/(2*m↑2)*(k'/k)↑2 we need to find
ε'εki + εε'kf kiεε' + kfε'ε
1/4 trace {(pf+m)(----- ------)(pi+m)(----- ------)}
2k.pi 2k'.pi 2k.pi 2k'.pi
A straightforward REDUCE program for this, with appropriate
substitutions would be:
ON DIV; COMMENT THIS GIVES US OUTPUT IN SAME FORM AS BJORKEN AND DRELL;
MASS KI= 0, KF= 0, PI= M, PF= M; VECTOR E;
COMMENT IF E IS USED AS A VECTOR, IT LOSES ITS SCALAR IDENTITY AS THE
BASE OF NATURAL LOGARITHMS;
MSHELL KI,KF,PI,PF;
LET PI.E= 0, PI.EP= 0, PI.PF= M↑2+KI.KF, PI.KI= M*K,PI.KF=
M*KP, PF.E= -KF.E, PF.EP= KI.EP, PF.KI= M*KP, PF.KF=
M*K, KI.E= 0, KI.KF= M*(K-KP), KF.EP= 0, E.E= -1, EP.EP=
-1;
FOR ALL P LET GP(P)= G(L,P)+M;
COMMENT THIS IS JUST TO SAVE US A LOT OF WRITING;
GP(PF)*(G(L,EP,E,KI)/(2*KI.PI) + G(L,E,EP,KF)/(2*KF.PI))
* GP(PI)*(G(L,KI,E,EP)/(2*KI.PI) + G(L,KF,EP,E)/(2*KF.PI)) $
WRITE "THE COMPTON CROSS-SECTION IS ",!*ANS;
This program will print the following result
(-1) (-1) 2
THE COMPTON CXN IS 1/2*K*KP + 1/2*K *KP + 2*E.EP - 1
%TOP,,,,R-1
REFERENCES
[1] Sconzo, P., LeSchack, A. R., and Tobey, R., Symbolic Computation
of f and g Series by Computer. Astronomical Journal 70 (May
1965).
[2] Collins, G. E., Journal of the A.C.M. 14, 128 (1967).
[3] Lipson, J. D., Symbolic Methods for the Computer Solution of
Linear Equations with Applications to Flowgraphs, Proceedings of
the 1968 Summer Institute on Symbolic Mathematical Computation,
IBM Programming Laboratory Report FSC 69-0312 (1969)
[4] Hearn, A. C., REDUCE 2, A System and Language for Algebraic
Manipulation, Proceedings of the Second Symposium on Symbolic
and Algebraic Manipulation (to be published)
[5] Hearn, A. C., REDUCE, A User-Oriented Interactive System for
Algebraic Simplification, Proceedings of the ACM Symposium on
Interactive Systems for Experimental Applied Mathematics, held
in Washington, D.C., August 1967.
[6] Hearn, A. C., The Problem of Substitution, Proceedings of the
1968 Summer Institute on Symbolic Mathematical Computation, IBM
Programming Laboratory Report FSC 69-0312 (1969)
[7] McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P. and
Levin, M. I., LISP 1.5 Programmer's Manual, M.I.T. Press, 1965
[8] Weissman, Clark, LISP 1.5 Primer, Dickenson, 1967
[9] Hearn, A. C., Standard LISP, Stanford Artificial Intelligence
Project Memo AI-90 (May 1969)
[10] Bjorken, J. D. and Drell, S. D., Relativistic Quantum Mechanics
(McGraw-Hill, New York, 1965).
[11] Chisholm, J. S. R., Il Nuovo Cimento X, 30, 426 (1963)
[12] Kahane, J., Journal Math. Phys. 9, 1732 (1968)